﻿using System.Collections.Generic;
using System.Linq;
using Algoritmia.StateSpaces;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.ExactCover
{
    public class DLX1StateSpace : IReversibleForwardStateSpace<DLX.State, DLX.Cell>
    {
        private readonly List<IEnumerable<int>> _ones;
        private readonly Lists.IList<int> _selected;
        private readonly int _n;
        private readonly int _m;

        public DLX1StateSpace(IEnumerable<IEnumerable<int>> ones, Lists.IList<int> selected = null)
        {
            var onesList = ones.ToList();
            _ones = onesList;
            _selected = selected ?? new int[] { }.ToAlgoritmiaList();
            _n = onesList.Count;
            _m = (from seq in onesList
                  select seq.Max()).Max() + 1;

        }

        #region Implementation of IForwardStateSpace<DLX.State,int>

        public DLX.State Decide(DLX.State state, DLX.Cell cellInRow)
        {
            state.Selected.Add(state.RowIndex[cellInRow]);
            foreach (DLX.One one in cellInRow.Right())
            {
                one.Head.Cover();
            }
            return state;
        }

        public IEnumerable<DLX.Cell> Decisions(DLX.State state)
        {
            var size = _n + 1;
            DLX.Column bestCol = null;
            foreach (DLX.Column column in state.Right())
            {
                if (column.S < size)
                {
                    size = column.S;
                    bestCol = column;
                }
                if (size == 1) break;
            }
            bestCol.Cover();
            foreach (var cellInRow in bestCol.Down())
            {
                yield return cellInRow;
            }
            bestCol.UnCover();
        }

        public IEnumerable<DLX.State> InitialStates
        {
            get { yield return new DLX.State(_ones, _selected, _n, _m); }
        }

        public bool IsFinal(DLX.State state)
        {
            return state.R == state;
        }

        #endregion

        #region Implementation of IReversibleForwardStateSpace<DLX.State,int>

        public DLX.State Undo(DLX.State state, DLX.Cell cellInRow)
        {
            state.Selected.Remove(state.RowIndex[cellInRow]);
            foreach (DLX.One one in cellInRow.Left())
            {
                one.Head.UnCover();
            }
            return state;
        }

        #endregion
    }
}
